The present invention generally relates to adaptive identification techniques. It is particularly well suited, though not exclusively, to use with echo cancellers used in telecommunications.
Adaptive identification of linear systems characterised by their impulse response has been widely studied and numerous algorithmic solutions have been proposed in specialist literature.
The general problem of direct identification by transverse adaptive filtering, which corresponds to the majority of practical applications, is considered.
FIG. 1 illustrates a system to be identified 10, to which a signal xt varying over time is applied. The response of the system 10 to the input signal xt is written as zt. Measurement of the response zt is inevitably accompanied by the addition of an interference component bt referred to as observation noise. This observation noise bt may comprise noise strictly speaking (white noise or traffic noise, for example), but also some useful signal. The component bt is referred to as observation noise because it interferes with the observation of the response zt. The adder 12 in the drawing symbolises the superposition of the component bt, assumed to be additive, to the response zt. The measured observation signal yt is therefore the response of a real system 14 comprising the system to be identified 10 and the adder 12.
The adaptive identification device 16 receives the input signal xt on a first input E1 and the observation signal yt on a second input E2. The signals xt and yt are amplified, filtered and digitised at the input of the device 16 by conventional elements, not illustrated. The adaptive identification device 16 has an identification filter 18 consisting of a programmable filter having a finite impulse response (FIR) expressed as             H              t        -        1            T        =          (                        h                      t            -            1                    0                ,                  h                      t            -            1                    1                ,        …        ⁢                                   ,                  h                      t            -            1                                L            -            1                              )        ,where (.)T denotes the matrix transposition. The coefficients of the identification filter 18 are adapted so that this impulse response Ht−1T is representative of the impulse response of the system to be identified 10. The filter 18 receives the digitised input signal xt and supplies an estimation {circumflex over (z)}t of the response zt of the system 10.
A subtractor 20 removes this estimation {circumflex over (z)}t from the digitised observation signal yt to supply an error signal et. This error signal et may be regarded as an estimation of the interference component bt.
A updating unit 22 of the identification filter adapts the coefficients of the filter 18 on the basis of the input signal xt and the error signal et, generally taking an adaptation step μ into account.
Numerous algorithms have been proposed to automatically determine the coefficients of the adaptive filter 18. When used in practice, the originators of these devices are generally forced to seek a compromise between the convergence speed of the algorithm, the ease with which it can be controlled, and run, the arithmetic complexity and numerical stability.
The LMS algorithm (<<Least Mean Square>>) is the algorithm most widely used to adapt the impulse response of a FIR identification filter continuously over time. Such algorithm provides an efficient implementation of a Wien filter with L coefficients which minimises the mean value of the power of the filtering error in the stochastic approximation. It is defined by the equations:et=yt−XtTHt−1  (1) Ht=Ht−1+μetXt  (2) where Xt=(xt, xt−1, . . . , xt−L+1)T represents the vector of the last L samples of the input signal and μ represents the adaptation step of the algorithm. The main advantages of this algorithm are its low numerical complexity, its ease of implementation and its robustness to errors. Unfortunately, if highly correlated signals (such as speech signals) are used to excite the unknown system, this algorithm has a convergence speed which deteriorates rapidly.
In order to get round these problems, a specific version of the LMS algorithm is often used, incorporating a parameter adjustable adaptation step.
This algorithm then corresponds to a normalised version of the LMS, or NLMS (<<Normalized Least Mean Square>>) in which the coefficients of the adaptive filter are updated according to the following equation:                               H          t                =                              H                          t              -              1                                +                                                    μ                ⁢                                                                   ⁢                                  e                  t                                                                              X                  t                  T                                ⁢                                  X                  t                                                      ⁢                          X              t                                                          (        3        )            
Assuming that the optimum filter Hopt of the unknown system 10 is a FIR filter of an order lower than or equal to L, equation (3) may be written:ΔHt=[I−μXt(XtTXt)−1XtT]ΔHt−1−μXt(XtTXt)−1bt  (4) where ΔHt=Hopt−Ht represents the error in the estimated coefficients of the filter at iteration t. This expression corresponds to a geometric interpretation of the NLMS algorithm. In situations where μ≠, equation (4) corresponds to a relaxed projection of the vector ΔHt−1 across an affine sub-space wholly determined by the matrix between the brackets and by knowing the initial shift imparted by the last term of equation (4).
In order to come up with new algorithms offering a higher convergence speed than that of the NLMS algorithm, several approaches have been proposed in the background literature (implementation in the frequency domain, sub-band filtering, . . . ). Below, we will look at those based on modifying the direction of the projection of the NLMS as well as those based on using a whitening filter.
Improving Convergence by Modifying the Direction of Projection
Convergence of the NLMS can be improved by modifying the direction of projection as mentioned above. This analysis is the basis of affine projection algorithms (APA) which are based on a projection of multiple order equal to P. As a result, the algorithms have much better convergence properties on correlated signals in comparison with the NLMS algorithm (which corresponds to the extreme case where P=1). The P-order APA algorithms (see K. Oseki et al., <<An adaptive algorithm using an orthogonal projection to an affine subspace and its properties>>, Electronics and communications in Japan, 1984, Vol. 67-A, no 5, pages 19-27) are characterised by updating the coefficients of the identification filter 18 according to the following equations:et,P=Yt,P−Xt,PHt−1  (5) Ht=Ht−1+μXt,P#et,P  (6)                 where:Xt,P=(Xt, Xt−1, . . . , Xt−P+1)T  (7) Yt,P=(yt, yt−1, . . . , yt−P+1)T  (8) in which et,P denotes the a priori error vector and Xt,P#=Xt,PT(Xt,PXt,PT)−1 represents the generalised inverse Moore-Penrose matrix of order L×P. With these equations for updating coefficients of the identification filter, it can be shown that the estimated a posteriori error vector et,Ppost is equal to:et,Ppost=Yt,P−Xt,PHt=(1−μ)et,P  (9)         
Assuming that the adaptation step of the algorithm is equal to unity, the P order affine projection algorithm cancels out the P a posteriori errors defined at equation (9). This latter property explains why the convergence behaviour of the algorithm is very good. Unfortunately, in the basic version described by equations (5) and (6), the theoretical complexity of such algorithms is in the order of 2LP+KinvP2 where Kinv represents a constant associated with the computation of the inverse matrix incorporated in equation (6), where the parameters L and P denote respectively the number of coefficients of the identification filter and the projection order.
In order to reduce this initial complexity, several fast versions of these algorithms have been proposed which involve segmenting the pseudo-autocorrelation matrix in a manner similar to the fast recursive least squares algorithms. Such techniques enable the initial complexity to be reduced to more reasonable values in the order of 2L+20P (see: Steven L. Gay, <<A fast converging, low complexity adaptive filtering algorithm>>, Proceedings of the 3rd International Workshop on Acoustic Echo and Noise Control, Plestin-Les-Grèves, France 1993, pages 223-226; Steven L. Gay, <<Fast projection algorithms with application to voice echo cancellation>>, Ph.D. Dissertation of the State University of New Jersey, USA, 1994; Steven L. Gay et al., <<The fast affine projection algorithm>>, Proceedings of ICASSP'95, pages 3023-3026, 1995; M. Montazéri, <<Une famille d'algorithmes adaptatifs comprenant les algorithmes NLMS et RLS: application à l'annulation d'écho acoustique>>, Thèse de Doctorat de l'Université de Paris Sud, 1994; M. Tanaka et al., <<Reduction of computation for high-order projection algorithm>>, Electronics Information Communication Society Autumn Seminar, Tokyo, 1993).
Improving Convergence with a Whitening Filter
Numerous research papers have been devoted to studying ways of improving the performance of adaptive identification systems using predictive structures (see: M. Mboup et al., <<LMS coupled adaptive prediction and system identification: a statistical model and transient analysis>>, IEEE Transactions on signal processing, Vol. 42, no 10, October 1994, pages 2607-2615; S. Benjebara, <<Caractéristiques des signaux et capacité de poursuite des non-stationnarités aléatoires: apport des schémas prédictifs et multirésolutions>>, Thèse de l'Université des Sciences, des Techniques et de Médecine de Tunis II, Tunis, 1997). Case studies have been able to demonstrate two main structures (symmetrical or non-symmetrical) for pre-whitening the excitation signal of the filter using an adaptive filtering technique. The general principle as to how the non-symmetrical structure is processed is illustrated in FIG. 2.
A structure of this type is essentially based on an empirical approach intended to modify the signal used to update coefficients of the adaptive filter and transform it so as to reduce the conditioning of its auto-correlation matrix (ratio between the maximum and minimum eigenvalues of the auto-correlation matrix of this signal). As a result, coefficients are updated by the adaptation module 22 using the signal available at the output of a linear prediction circuit 24, whereby the prediction is performed from M coefficients. The algorithm applied by the module 22 to update the L coefficients of the identification filter 18 corresponds to the LMS (equation (2)) or to the NLMS (equation (3)). Similarly, the prediction circuit 24 is implemented as an adaptive filter with M coefficients which are updated with the aid of an LMS algorithm.
Studies devoted to analysing the performance obtained from this type of structure have specifically highlighted the existence of a very strong interaction between the prediction and adaptation modules of the system. In particular, this leads to an inter-dependence between the coefficient adaptation equations of the adaptive predictor 24 and those of the identification filter 18. This strong dependence also occurs in the choice of the two adaptation steps μP and μH, which creates a zone of very low stability of the entire structure.
As a result, the authors mention an instability of the entire predictive structure identification system, which limits the prediction orders used in the implementations to values which are always less than four so as to ensure a relative stability, thereby limiting the identification performance: it is necessary to select very low adaptation steps μP and μH which are not compatible with the aim of improving convergence speed.
Reviewing the solutions proposed in the literature to improve the convergence speed of adaptive identification algorithms leads to the conclusion that on the one hand the algorithms based on modifying the projection direction remain complex in terms of the number of arithmetical operations needed to update the filter coefficients if the projection order P is high and that, on the other hand, the predictive structure identification schemes remain very delicate in terms of control and offer a reduced gain in convergence because of the low prediction orders M used in practice to ensure that the global structure remains relatively stable.
An object of the present invention is to propose a method of adaptive identification which has good convergence properties and which is relatively simple to implement, with a limited arithmetic complexity.